package com.algrithom.find;

import java.util.Arrays;

/**
 * 1231. 分享巧克力
 * 
 * @author think
 */
public class Solution1 {
    
    public static void main(String[] args){
        int[] array = new int[]{1,2,3,4,5,6,7,8,9};
        Solution1 solution1 = new Solution1();
        System.out.println(solution1.maximizeSweetness(array,5));
    }
    
    public int maximizeSweetness(int[] sweetness,int K){
        int ans = 0;
        int l = 0;
        if (K == 0) {
            return Arrays.stream(sweetness).sum();
        }
        int r = Arrays.stream(sweetness).sum() / K;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (check(sweetness,mid,K)) {
                ans = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return ans;
    }
    
    private boolean check(int[] sweetness,int sum,int k){
        int nowsum = 0;
        int num = 0;
        for (int i = 0; i < sweetness.length; i++) {
            nowsum += sweetness[i];
            if (nowsum >= sum) {
                num++;
                nowsum = 0;
            }
        }
        return num >= k + 1;
    }
}